googologywikiaorg-20200223-history
User blog:LittlePeng9/First order oodle theory
Please refer to this blog post, perhaps after finishing reading this post. ---- So in this blog post I'm going to formalize notion of oodles. Because of multitude of paradoxes which appear when we try to think of oodles as "collections of anything", I've decided to build a hierarchial structure out of them. Note that what I'm describing here isn't supposed to be subject of generalization, but I still decided (for one or other reason) to call it first order oodle theory. Oodles Oodles are abstract objects, analoguous to sets, which, in a way, have a broader meaning. The language of FOOT is going to have infinite set of variables, oodle connectives \(\in, =\) and some standard set of logical connectives, say \(\exists,\land,\neg\). We define truth of formula under some variable assignment using standard Tarskian definition of truth: *Formula is of the form \(x\in y\) for x,y variables, is true iff x is an element of y under assignment of variables. *Formula is of the form \(x=y\) for x,y variables, is true iff x and y have the same oodle assigned. *Formula \(\varphi\land\psi\) is true iff both \(\varphi\) and \(\psi\) are true under the assignment. *Formula \(\neg\varphi\) is true iff formula \(\varphi\) isn't true. *Formula \(\exists x:\varphi(x)\) is true iff we can find oodle X for which formula \(\varphi(X)\) is true. We also assume that oodles satisfy all the properties which are considered "natural" properties, e.g. extensionality or existence of full power set. Oodle ranks To avoids all possible paradoxes, we will want oodles to be well-founded - there is no infinite chain of oodles such that \(A_1\ni A_2\ni...\). Because of this, we have naturally arising notion of rank of oodle, defined as follows: *If \(A\) is empty oodle, then \(A\) is its own rank. *If \(A\) has an element with rank \(B\), such that rank of every element of \(A\) is either \(B\) or its element, then \(A\) has rank \(B\cup\{B\}\). *If \(A\) has no elements like the above one, then rank of \(A\) is union of ranks of its elements. From now on, we will say that rank \(A\) is smaller than rank \(B\) if \(A\in B\), and that \(A\) is at most \(B\) if it's either smaller or equal. We are going to refer to possible ranks as oodinals, and we are going to denote them with greek letters. Oodinals can be equivalently defined as transitive oodles which are well-ordered by \(\in\). Let denote \(\alpha\cup\{\alpha\}=\alpha+1\), and call such oodinal a successor oodinal. If \(\beta>0\) is not successor, then it's limit oodinal. It's quite easy to prove that each oodle has a rank - by contradiction, of some oodle \(A_1\) had no rank, then it would have to have an element \(A_2\) without rank, and continuing we would have infinite descending sequence \(A_1\ni A_2\ni...\) which we claimed do not exist. Oodle hierarchy Let's denote the oodle of all oodles of rank smaller than \(\alpha\) as \(V_\alpha\). We can see, from definition above, see that if \(\alpha<\beta\) then \(V_\alpha\subset V_\beta\), and that \(V_{\alpha\cup\{\alpha\}}\) is exactly the oodle of all oodles elements of which have rank at most \(\alpha\). Because of this, we can define these equivalently as a hierarchy: *\(V_\varnothing=\varnothing\) *\(V_{\alpha+1}=\mathcal{P}(V_\alpha)\) *\(V_\alpha=\bigcup_{\beta<\alpha} V_\beta\) for limit \(\alpha\) Let's call \(V=\bigcup V_\alpha\) the oodleverse. This structure, while unfortunatelly not an oodle, contains all oodles, because we've shown that each of them has a rank. Sets? A question arises: how to define sets inside this structure? Turns out, it's impossible. Firstly, because "sets" don't even have definition, secondly, oodleverse could as well work out as a universe of sets. However, if we had some quite large oodinal, which we'll denote \(\text{Ord}\), we could define sets as oodles which have rank \(<\text{Ord}\). We will also call elements of \(\text{Ord}\) ordinals. But the problem now could be, how to choose \(\text{Ord}\)? Because we want these sets to satisfy some natural properties, we can't choose it in any way we want. Also, because we know that \(V\) can work as the universe of sets, we want \(V_\text{Ord}\) to satisfy the same statements about sets as \(V\) does about oodles, counting only formulas with parameters in \(V_\text{Ord}\) (we want it to be elementary substructure). Here is how we can construct such oodinal \(\text{Ord}\): \(\alpha_0\) is the least oodinal which, for every formula \(\varphi\) without parameters, satisfies "if there exists oodinal \(\alpha\) such that \(\varphi(\alpha)\), then there is oodinal \(\beta<\alpha_0\) such that \(\varphi(\beta)\)". Then, if we already have \(\alpha_n\) defined, we define \(\alpha_{n+1}\) as the least oodinal which, for every formula \(\varphi\) and finite collection \(A\) of parameters from \(V_{\alpha_n}\), satisfies "if there exists oodinal \(\alpha\) such that \(\varphi(\alpha,A)\), then there is oodinal \(\beta<\alpha_{n+1}\) such that \(\varphi(\beta,A)\). Now we define \(\text{Ord}=\lim_{n\rightarrow\omega}\alpha_n\) Now we have to verify that formula \(\varphi(A)\), for \(A\in V_\text{Ord}\) is true in \(V\) iff it is in \(V_\text{Ord}\). The verification goes by induction on structure of formula, with only tricky case being existential quantifier. So let \(\varphi(A)\) have form \(\exists x: \phi(x,A)\). Assume this holds in \(V\). Then, there exists \(X\) such that \(\phi(X,A)\) holds in \(V\). But then, rank of \(X\) satisfies "there exists \(x\) with this rank which makes \(\phi(x,A)\) true". Because \(A\in V_\text{Ord}\), \(A\in V_{\alpha_n}\) for some \(n\). So, by construction, there exists an ordinal \(\beta<\alpha_{n+1}<\text{Ord}\) which satisfies the formula, so there exists \(X'\) with rank below \(\text{Ord}\), thus in \(V_\text{Ord}\), which makes \(\phi(X',A)\) true, so formula \(\varphi(A)\) holds in \(V_\text{Ord}\). Conversely, assume \(\exists x: \phi(x,A)\), and let \(\phi(X,A)\). By inductive assumption, as \(\phi(X,A)\) holds in \(V_\text{Ord}\), it holds in \(V\), so \(\varphi(A)\) holds in \(V\). Extending the language So now that we have a definition of \(\text{Ord}\), and from it derived definitions of sets and ordinals, we would want to use it in our FOOT, to make it stronger than FOST. Unfortunatelly, for quite clear reasons, we cannote define \(\text{Ord}\) in FOOT. However, we can add it as a constant symbol (if we were building axiomatization, then we would also add a class of axioms "if \(\phi(x)\) defines unique oodinal, then this oodinal is smaller than \(\text{Ord}\)" for every formula \(\phi\) not using symbol \(\text{Ord}\). Now we can define sets in FOOT as these oodles which have rank below \(\text{Ord}\), equivalently these in \(V_\text{Ord}\). But we know that collections of sets are also oodles, and actually these are the oodles appearent in \(V_{\text{Ord}+1}\). Because of this, we can now define truth predicate for set theory, in a way exactly the same as in this blog post. It follows that we can now also define Rayo's function in FOOT, and thus diagonalize over it and what not. So we can effectively simulate SOST in FOOT. Further, we can also define collections of classes, which will be elements of \(V_{\text{Ord}+2}\), thanks to which we can define truth predicate for SOST, and we will also be able to define \(\text{Rayo}_2\) function. And we can continue! Because we can define oodinals up to \(\text{Ord}+\omega\), we can define \(\text{Rayo}_\omega\) too, but this of course is far from the boundaries of possibilities. We can actually define \(\text{Ord}2=\text{Ord}+\text{Ord}\), and by using oodles up to there we can have even OOST embeded in FOOT! And we have added only one constant symbol. Of course, we can continue, and this way we could define things like \(\text{Ord}^2,\text{Ord}^\text{Ord},\Gamma_{\text{Ord}+1}, \omega^\text{CK}_{\text{Ord}+1}\) and so on and so on. "Limit to all of this is..."? Just as with sets, we now have an issue, because we cannot really define in FOOT what we mean by "limit to all of this". Again, we would have to define externally what could possibly be the limit. And, similarly as above, we are going to define another oodinal, \(\text{Ord}_2\), as least ordinal beyond anything we can define when we are only able to use \(\text{Ord}\). Exact construction is the same as before, except we can use \(\text{Ord}\) as a constant symbol or a parameter. Just as before, \(V_{\text{Ord}_2}\) will satisfy the same statements about oodles as \(V\) does. Extending the language further Of course, we will want to add this \(\text{Ord}_2\) to our language as a constant symbol. Now we will be able to make truth predicate about \(V_{\text{Ord}_2}\), which are the same truths as in \(V\), provided the formula doesn't use \(\text{Ord}_2\). The language we are making truth predicate for is essentially the O2OST of the other blog post. Of course, we can now continue with defining \(\text{Ord}_3\), \(\text{Ord}_4\),... But we don't want to add infinitely many constant symbols, because then we might have infinitely many formulas of bounded length. To save this, I'm going to use a similar trick as I used elsewhere - we are going to introduce special symbols, say, square brackets ,, and the idea is, when we have variable x, which takes oodinal value \(\alpha\), then x is supposed to mean the oodinal \(\text{Ord}_\alpha\), where we define these oodinals by transfinite recursion as follows: : \(\text{Ord}_\alpha\) is the least oodinal which is greater than every ordinal which can be defined in language of FOOT with parameters of rank below \(\text{Ord}_\alpha\), if we allow it to use constant symbols \(\text{Ord}_\beta\) for every \(\beta<\alpha\). Although the definitions seems circular, we can still talk about oodinals which satisfy it. Construction from the beginning can be generalized to actually construct such oodinal. Here we don't really have to care if language would have infinitely many symbols. Of course, in the language in the definition there are might be constant symbols which cannot be defined using x notation, but it won't infer anything, only it will make \(\text{Ord}_\alpha\) larger. If x doesn't take oodinal value in given variable assignment, then we can say that every atomic formula (i.e. one of form \(x\in y\), \(x=y\)) involving x is false. Function! Some of you might think, "How the hell is this googology-related?", and this is how the hell this is googology related: : Define \(\text{FOOT}(n)\) as the largest natural number which can be defined in the language of FOOT in at most \(n\) symbols. Here "natural number" is a finite Von Neumann's ordinal, "largest" is meant in sense of set inclusion, and "defined" means that there exists a formula which using at most \(n\) symbols which is true exactly for this number. There are obvious similarities between this function and Rayo's function, except that the language of FOOT is richer, and allows us to define much more stuff! In this blog post I have investigated some extensions to Rayo's function (up to OOST it even makes sense), and there you can see how all the truth predicates are defined, and they already show how much stronger this language is. But FOOT goes, in formal way, beyond what I tried to explain there. Of course, there is no reason to stop at x. We could define {0} as the least ordinal which is undefinable in any way using [ ], then {1} as least beyond , and {0} and so on. We can define {x} for general x, then go with <0>, <1>, , and what not, then we could go and make it into array notation, like 1,0, x,y,z, a,b,c,..., maybe even make it into some collapsing function \(\xi\)! We could get things like \(\xi(\Omega\), \(\xi(\xi_0(I))\) or \(\xi(\epsilon_{K+1})\). Maybe even analogue of Taranovsky's notation can be made out of this? But I want to say: I'm NOT doing any of the above. I'm just throwing possibilities there. I don't want to make it into array notation, because it will just get, in a way, boring. I consider such extensions very artificial, and for comparison I will point out to Aarex's hydra. At first it's really nice - nodes labelled with other hydras, but then it becomes simply an another array notation under hydra's coat. There is more of array rules than simple head cutting. I cannot say that this is a weak or naive extension - indeed, it is quite powerful. But couldn't we just left it as it was? This is exactly what I'm doing here - leaving this as it is before it turns into a dumb array notation which, while indeed adding a lot of power, would make it unnecessarily complicated. I'm sure there are other ways to go far beyond all of these ideas without making all the definitions ten times as long. Number! Okay, so when defining some extremely fast growing function, it's worth defining some extremely large number. I'll go for the following one: : \(\text{FOOT}^{10}(10^{100})\) With just one application of the function we can get to Rayo number, and very likely well beyond. And now we have that many symbols to define all the truth predicates we want, until we get really sick of them. And then we just make 8 more applications. So, uhhh, I guess I just made the biggest number in the existence. I've decided to name this number BIG FOOT, name suggested by Sbiis which I find really fitting the topic. Self-contained definition Let the language be standard language of set theory augmented with symbols [ and ], i.e. the language consists of countably infinite number of distinct variables, symbols \( (,),\land,\neg,\exists,\in,=,,\), and let all but the last two be the subject to standard rules of formula construction and Tarskian definition of truth (with the last two symbols to be explained in a second). Let elements of universe of discourse be called oodles, and let \(\in\)-transitive oodles well-ordered by \(\in\) be called oodinals. From now, whenever talking about "larger" or "smaller" oodinals, we mean it in the sense of inclusion. Let \(V_\varnothing\) be empty oodle, and for oodinal \(\alpha\neq\varnothing\) define \(V_\alpha=\bigcup_{\beta<\alpha}\mathcal{P}(V_\beta)\), where \(\mathcal{P}(X)\) denotes oodle of all suboodles of \(X\). For every oodinal \(\alpha\) we define \(\text{Ord}_\alpha\) as follows: let's start with oodinal \(\alpha_0\) which satisfies, for every parameter-free formula \(\varphi\) in language of set theory augmented by constant symbols for \(\text{Ord}_\beta\) for all \(\beta<\alpha\), "if there exists oodinal \(\alpha\) such that \(\varphi(\alpha)\), then there is oodinal \(\beta<\alpha_0\) such that \(\varphi(\beta)\)". Then, if we already have \(\alpha_n\) defined, we define \(\alpha_{n+1}\) as the least oodinal which, for every formula \(\varphi\) in the same language as above and finite collection \(A\) of parameters from \(V_{\alpha_n}\), satisfies "if there exists oodinal \(\alpha\) such that \(\varphi(\alpha,A)\), then there is oodinal \(\beta<\alpha_{n+1}\) such that \(\varphi(\beta,A)\). Now we define \(\text{Ord}_\alpha=\lim_{n\rightarrow\omega}\alpha_n\). Now we add a new formula formation rule: if x is a variable, then x is subject to same rules as a variable, but it isn't subject to truth assignment. We also extend Tarskian truth by the following rules: If in variable assignment x takes value \(\alpha\) which is an oodinal, and y takes any value \(A\), then we set formula 'y\(\in\)x' true iff \(A\in V_{\text{Ord}_\alpha}\), and we set 'y=x' true iff \(A=V_{\text{Ord}_\alpha}\). In case x doesn't take oodinal value, in both cases formulas are set to false. Let "natural number" be an oodinal which is finite (i.e. every injection from it to itself is bijection). Definition of an oodle \(A\) is a formula \(\phi(x)\) such that \(\phi(X)\Leftrightarrow X=A\). Length of a formula is understood in obvious way. For natural number \(n\) we define \(\text{FOOT}(n)\) as the largest natural number \(N\) such that there exists a definition of \(N\) using at most \(n\) symbols. ---- Please refer to this blog post. Category:Blog posts